Among the circuits for carrying out arithmetical operations of multiplication, multipliers having a typical, iterative structure or architecture known as a "cellular array" have been found to be especially advantageous.
Assuming that two integers expressed in natural binary form with 4 parallel-supplied bits are to be multiplied together, EQU A=a.sub.3 *2.sup.3 +a.sub.2 *2.sup.2 +a.sub.1 *2+a.sub.0 EQU B=b.sub.3 *2.sup.3 +b.sub.2 *2.sup.2 +b.sub.1 *2+b.sub.0
then the product is, EQU A*B=b.sub.0 (a.sub.3 *2.sup.3 +a.sub.2 *2.sup.2 +a.sub.1 *2+a.sub.0)+ EQU 2b.sub.1 (a.sub.3 *2.sup.3 +a.sub.2 *2.sup.2 +a.sub.1 *2+a.sub.0)+ EQU 4b.sub.2 (a.sub.3 *2.sup.3 +a.sub.2 *2.sup.2 +a.sub.1 *2+a.sub.0)+ EQU 8b.sub.3 (a.sub.3 *2.sup.3 +a.sub.2 *2.sup.2 +a.sub.1 *2+a.sub.0)
Therefore, the product of A by B is obtained by adding together the partial products wherein the terms making up the following matrix appear: ##EQU1##
There are several different types of algorithms whereby the sum of the partial products thus computed can be reckoned. Iterative array multipliers consist of a combinatorial network which performs this addition with a delay which is only dependent on the time required to go through the various logic circuits.
The computation of the matrix of partial products is accomplished using a combinatorial network of logic AND gating circuits whereby all the matrix bits are obtained simultaneously with just the delay of a simple logic product. If the size of the operands is of n bits, then n*n AND gates will be required.
There are several circuit architectures that can provide the sum of the individual logic products making up the partial product matrix. Of considerable import is Dadda's algorithm, described in an article entitled "Some Schemes for Parallel Multipliers", Alta Frequenza, Vol. XXXIV, No. 5, May 1965, which yields the sum of the individual partial products by compressing the matrix columns, that is progressively reducing the number of the rows which make up the partial product matrix by adding together the bits in one column until two rows only are obtained whose sum, representing the result of the multiplication, is obtained using a fast adder. Thus, the multiplier is composed of three parts: the matrix structure of AND gates which is to compute the partial products, the circuit for compressing the columns, and the final adder.
For effecting the column compression portion of the procedure, parallel counters may be used, that is components which will count the number of bits equal to 1 present at their inputs; where two inputs only are provided, these would be so-called Half-Adders ("HA"), whereas with three inputs provided, these would be so-called Full Adders ("FA"). However, they may also be defined for any number of inputs greater than three.
Dadda uses both FAs and HAs in his multiplier, and shows that the best method (i.e., that requiring the smallest number of cells) consists of compressing the columns such that the number of rows which make up the partial product matrix decreases in accordance with the following recursive formula: EQU d(0)=2 EQU d(+1)=3/2d(k)
where, d(i) is the number of rows in the i-th stage, and k is the number of stages required for the reduction.
Thus, the following series is generated:
______________________________________ 0 1 2 3 4 5 6 7 8 9 ______________________________________ d(k) 2 3 4 6 9 13 19 28 42 63 ______________________________________
For example, in the 8.times.8 case, the initial number (8) of the rows must be reduced to 6, 4, 3, and ultimately 2; accordingly, 4 stages are required.
The algorithm provides for the use of FAs and HAs arranged in a structure which ensures that no more than d(k) rows exist in the k-th stage.
Also described in the article is Wallace's block diagram, and reflections are offered on the parallel adders used in binary number multipliers.
In another, more recently published article by L. Dadda, entitled "On Parallel Digital Multiplier", Alta Frequenza, Vol. XLV, No. 10, October 1976, the parallel implementation of the adders is dealt with, using "fast" storage elements to provide high-speed digital multipliers.
The technique employed for multiplying natural binary numbers may also be used for relative numbers, expressed in binary form, by representing the negative value numbers in the two's complement binary form. The necessary add operation is carried out by two's complementing the negative terms. This allows the complexity of the arithmetic circuits of a processor to be greatly reduced and, accordingly, the speed of operation increased.
Known are natural number multipliers, two's complement binary number multipliers, and multipliers which either enable two natural binary numbers or two's complement binary numbers to be multiplied together.
However, there is an unmet need in the art for a multiplier circuit for accomplishing multiplication operations with two binary operands, each operand either in the natural or two's complement form, as desired.